#define _CRT_SECURE_NO_WARNINGS 1


//#include<vector>
//#include<string>
//#include<map>
//#include<iostream>
//
//using namespace std;
//
//bool Func(map<string, int>& hash, map<string, int>& hash_words)
//{
//	auto it1 = hash.begin();
//	auto it2 = hash_words.begin();
//	while (it1 != hash.end() && it2 != hash_words.end())
//	{
//		if (it1->first != it2->first || it1->second != it2->second)
//		{
//			return false;
//		}
//		it1++;
//		it2++;
//	}
//	return true;
//}
//
//vector<int> findSubstring(string s, vector<string>& words)
//{
//	map<string, int> hash_words;
//	for (auto& e : words)
//	{
//		hash_words[e]++;
//	}
//	int len = words[0].size();
//	int size = s.size();
//	int left = 0, right = 0, count = 0;
//	vector<int> v;
//	for (int i = 0; i < len; i++)
//	{
//		left = right = i;
//		map<string, int> hash;
//		count = 0;
//		while (right + len <= size)
//		{
//			string str1(s.begin() + right, s.begin() + right + len);
//			hash[str1]++;
//			count++;
//			while (count == words.size())
//			{
//				if (Func(hash, hash_words))
//				{
//					v.push_back(left);
//				}
//				string str2(s.begin() + left, s.begin() + left + len);
//				hash[str2]--;
//				count--;
//				if (hash[str2] == 0)
//				{
//					hash.erase(str2);
//				}
//				left += len;
//			}
//			right += len;
//		}
//	}
//	return v;
//}

//int main()
//{
//	string s = "barfoofoobarthefoobarman";
//	vector<string> v = { "bar","foo","the" };
//	vector<int> ret = findSubstring(s, v);
//	for (auto& e : ret)
//	{
//		cout << e << ' ';
//	}
//	cout << endl;
//
//	return 0;
//}


#include<vector>
#include<iostream>

using namespace std;

int lengthOfLIS(vector<int>& nums)
{
    int size = nums.size();
    vector<int> dp(size, 1);
    int val = 1;
    for (int i = 1; i < size; i++)
    {
        for (int j = 0; j <= i - 1; j++)
        {
            if (nums[j] < nums[i])
            {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        val = max(val, dp[i]);
    }
    return val;
}

int main()
{
    vector<int> v = { 10,9,2,5,3,7,101,18 };
    cout << lengthOfLIS(v) << endl;

	return 0;
}